1. Field of the Invention
The present invention relates to the field of integrated circuit (IC) design. More specifically, the present invention relates to circuit simulation.
2. Background Information
Circuit simulation involves taking a description of a circuit, usually called a netlist, and a description of the input stimulus and then solving certain mathematical equations to determine the response of the circuit to the given input stimulus over the simulation time period. An example of a circuit simulator is the SPICE simulator, originally developed by W. Nagel. See e.g. W. Nagel, xe2x80x9cSPICE2, A computer program to simulate semiconductor circuitsxe2x80x9d, University of California, Berkeley, Memo No. ERL-M520, May 1975. Circuit simulators like SPICE represent a circuit as a set of coupled first order non-linear differential equations. Well-known techniques like Modified Nodal Analysis are used to perform this mathematical representation. The set of coupled non-linear equations are then solved using a sequence of steps, as illustrated in FIG. 10. The steps involve determining the time-step of integration, linearising the differential equations, and solving the resulting set of linear algebraic equations. A test is performed to determine if convergence has been achieved. The process is repeated till convergence is reached. Once convergence has been achieved, time is advanced and the entire process is repeated.
This traditional method of circuit simulation has a time complexity of O(N3) in the worst case, and O(N1.5) in the average case. This is due to the step involving the solution of the linear algebraic equations. This solution requires solving a matrix which has the time complexity of O(N3). Due to this super-linear time complexity of the algorithm in circuit simulators like SPICE, they are incapable of solving large circuits. Usually the limits of such simulators are reached when circuit sizes reach 100,000 devices. Solving circuits larger than this size becomes impossible, since the time taken to find the solution becomes very large.
The need to solve large circuits is becoming ever more important due to the advances of silicon process technology. Integrated circuits or chips with multi-million transistors are quite common. In order to address this need, alternative algorithms have been developed. For example, algorithms developed by C. X Huang etc, as disclosed in C. X. Huang et al., xe2x80x9cThe design and implementation of Powermillxe2x80x9d, Proceedings of the International Symposium on Low Power Design, pp. 105-120, 1995, by Y.-H. Shih etc as disclosed in Y. H. Shin et al., xe2x80x9cILLIADS: A new Fast MOS Timing Simulator Using Direct Equation Solving Approacgxe2x80x9d Proceedings of 28th ACM/IEEE Design Automation Conference, 1991, and by A. Devgan as disclosed in A. Devgan, xe2x80x9cTransient Simulation of Integrated Circuits in the Charge-Voltage Planexe2x80x9d, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VI. 15, No. 11, November 1996. These algorithms are characterized by a linear O(N) time complexity, thereby allowing them to handle large circuits.
The linear time complexity in these algorithms is achieved by partitioning the circuit into small partitions. To avoid the super-linear time of matrix solution, these algorithms use an approximate (i.e. inaccurate) solution instead. Under Huang""s approach, an algorithm called one-step relaxation is used. This algorithm often has inaccuracies of up to 20% and has serious problems on stiff circuits. In common circuits, relaxation based algorithms do not obtain the correct results. Circuits characterized by tight feedback or coupling cause problems for this algorithms. Under Shih""s approach, a direct equation solving technique is used. This works well in very limited situations where the device models can be accurately modeled by the second-order Shichman and Hodges model. This is rarely true with the latest silicon process technologies that require the very complex and highly non-linear BSIM3 models for accurate device models. Devgan uses an explicit integration technique but as evidenced from the waveforms in this paper, the accuracy is inadequate. The common problem with using any approximate algorithm for solving the matrix equations is that accuracy is usually not consistently good for all circuit design styles, especially for stiff circuits.
Standard matrix based algorithms do not suffer from the inaccuracy of relaxation and other approximate algorithms. Using matrix based algorithms along with partitioning can result in good accuracy; only the nodes at the boundaries of partitions can have degraded accuracy. However, use of single time-step for all partitions produces significantly reduced performance.
Thus, an improved approach to circuit simulation is desired.
An EDA tool is provided with a circuit simulator that simulates circuit operation using dynamic partitioning and on-demand evaluation. The circuit simulator includes a static partitioner, a dynamic partitioner and an evaluation scheduler. The static partitioner pre-forms a number of static partitions for the circuit. During simulation, the dynamic partitioner forms and re-forms a number of dynamic partitions, referencing the static partitions. At each simulation time step, the evaluation scheduler determines which, if any, of the dynamic partitions have to be evaluated, and evaluating on-demand only those where evaluations are necessary.
In one embodiment, the static partitioner forms the static partitions by organizing devices of the IC design into connected sets. The static partitioner also pre-processes the static partitions into a form tailored to the dynamic partitioner""s needs. In one embodiment, the dynamic partitioner determines if the devices of the IC design are in an On or an Off state, and forms the dynamic partitions accordingly. In one embodiment, the evaluation scheduler determines whether any of the dynamic partitions are in steady state, and schedules the dynamic partitions for evaluation accordingly. In one embodiment, the evaluations, when performed, are performed through matrix solution when accuracy is needed.